package my.jwds.p1606;

import java.util.*;

public class BusiestServers {

    public static void main(String[] args) {

        BusiestServers obj = new BusiestServers();
        long start = System.currentTimeMillis();
        System.out.println(obj.busiestServers1(3,new int[]{1,2,3,4,5},new int[]{5,2,3,3,3}));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }


    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {

        int[] times = new int[k];
        int max = 0,n = arrival.length;
        int[]counts = new int[k];

        for (int i = 0; i < n; i++) {
            addTheIdle(arrival[i],load[i],i%k,times,counts);
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < counts.length; i++) {
            if (max < counts[i]){
                max = counts[i];
                res.clear();
                res.add(i);
            }else if (max == counts[i]){
                res.add(i);
            }
        }
        return res;
    }

    void addTheIdle(int time,int load,int index,int[]times,int[] counts){

        for (int i = index; i < times.length; i++) {
            if (times[i] <= time){
                times[i] = time+load;
                counts[i]++;
                return;
            }
        }

        for (int i = 0; i < index; i++) {
            if (times[i] <= time){
                times[i] = time+load;
                counts[i]++;
                return;
            }
        }

    }
    public List<Integer> busiestServers1(int k, int[] arrival, int[] load) {
        TreeSet<Integer> idle = new TreeSet<>();
        for (int i = 0; i < k; i++) {
            idle.add(i);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        int[] counts = new int[k];
        int n = arrival.length;
        for (int i = 0; i < n; i++) {
            while(!queue.isEmpty() && queue.peek()[0] <= arrival[i]){
                idle.add(queue.poll()[1]);
            }

            if (idle.isEmpty())continue;


            Integer index = idle.ceiling(i % k);
            if (index == null)index = idle.first();
            queue.add(new int[]{arrival[i]+load[i],index});
            counts[index]++;
            idle.remove(index);


        }
        int max = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < counts.length; i++) {
            if (max < counts[i]){
                max = counts[i];
                res.clear();
                res.add(i);
            }else if (max == counts[i]){
                res.add(i);
            }
        }
        return res;
    }

}